package cn.le.hash;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 一致性hash实现
 *  https://crossoverjie.top/JCSprout/#/algorithm/consistent-hash-implement
 *
 * 特点:
 * 构造一个 0 ~ 2^32-1 大小的环。
 * 服务节点经过 hash 之后将自身存放到环中的下标中。
 * 客户端根据自身的某些数据 hash 之后也定位到这个环中。
 * 通过顺时针找到离他最近的一个节点，也就是这次路由的服务节点。
 * 考虑到服务节点的个数以及 hash 算法的问题导致环中的数据分布不均匀时引入了虚拟节点。
 *
 * 流程如下：
 * 初始化一个长度为 N 的数组。
 * 将服务节点通过 hash 算法得到的正整数，同时将节点自身的数据（hashcode、ip、端口等）存放在这里。
 * 完成节点存放后将整个数组进行排序（排序算法有多种）。
 * 客户端获取路由节点时，将自身进行 hash 也得到一个正整数；
 * 遍历这个数组直到找到一个数据大于等于当前客户端的 hash 值，就将当前节点作为该客户端所路由的节点。
 * 如果没有发现比客户端大的数据就返回第一个节点（满足环的特性）。
 *
 */
public class SortArrayMap {

    /**
     * 核心数组
     */
    private Node[] buckets;
    private static final int DEFAULT_SIZE = 10;
    /**
     * 数组大小,用它来存放服务节点的 hashcode 以及 value 值。
     */
    private int size= 0;

    public SortArrayMap(){
        buckets = new Node[DEFAULT_SIZE];
    }

    public void add(Long key,String value){
        checkSize(size + 1);
        Node node = new Node(key,value);
        buckets[++size] = node;
    }
    private void checkSize(int size){
        if (size >= buckets.length){
            //扩展自身的3/2
            int oldLen = buckets.length;
            int newLen = oldLen + (oldLen >> 1);
            buckets = Arrays.copyOf(buckets,newLen);
        }
    }
    /**
     * 排序
     */
    public void sort(){
        Arrays.sort(buckets, 0, size, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.key > o2.key){
                    return 1;
                }else {
                    return -1;
                }
            }
        });
    }
    /**
     * 顺序针取出
     */
    public String firstNodeValue(long key){
        if (size == 0){
            return null;
        }
        for (Node bucket : buckets){
            if (bucket == null){
                continue;
            }
            if (bucket.key >= key){
                return bucket.vlaue;
            }
        }
        return buckets[0].vlaue;
    }

    public static void main(String[] args) {



    }


    /**
     * 数据节点
     */
    private class Node{
        public Long key;
        public String vlaue;

        public Node(Long key, String vlaue) {
            this.key = key;
            this.vlaue = vlaue;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", vlaue='" + vlaue + '\'' +
                    '}';
        }
    }
}
